





<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 14, Exercise 9<BR>

<BR>

</H1>



Using the substitution method, we get

<br><br>

<em class=var>t(k)</em>

= <em class=var>4t(k-1) + c</em><br>

= <em class=var>4<sup>2</sup>t(k-2) + c(4 + 1)</em><br>

= <em class=var>4<sup>3</sup>t(k-3) + c(4<sup>2</sup> + 4 + 1)</em><br>

= <em class=var>4<sup>4</sup>t(k-4) + c(4<sup>3</sup> + 4<sup>2</sup> + 4 + 1)</em><br>

.<br>

.<br>

.<br>

= <em class=var>4<sup>k</sup>t(0) + c(4<sup>k-1</sup> + 4<sup>k-2</sup> + ... + 4 + 1)</em><br>

= <em class=var>4<sup>k</sup>d + c(4<sup>k</sup> - 1)/3</em><br>

= <em class=var>d * size<sup>2</sup> + c(size<sup>2</sup> - 1)/3</em><br>

= Theta(<em class=var>size<sup>2</sup></em>)



</FONT>

</BODY>

</HTML>

